package com.yulan.Array;

import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

/**
 * 287. 寻找重复数
 */
public class LeetCode_287 {
    public int findDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0;i<nums.length;i++){
            if(set.contains(nums[i])) return nums[i];
            set.add(nums[i]);
        }
        return -1;
    }

    /**
     *
     * 双指针法（是真滴秀）
     */
    public int findDuplicate2(int[] nums){
        int slow = 0;
        int fast = 0;
        slow = nums[slow];
        fast = nums[nums[fast]];
        while(slow!=fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        int prev1 = 0;
        int prev2 = slow;
        while(prev1 != prev2){
            prev1 = nums[prev1];
            prev2 = nums[prev2];
        }
        return prev1;
    }

    @Test
    public void test(){
        int[] arr = {1,3,4,2,2};
        System.out.println(findDuplicate(arr));
    }
}
